4
4.0

Sep 22, 2013
09/13

by
Amitabh Basu

######
4

######
0

######
0

We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem.

Source: http://arxiv.org/abs/1210.6732v2

16
16

Jul 20, 2013
07/13

by
Amitabh Basu

######
16

######
0

######
0

We study a mixed integer linear program with m integer variables and k non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [Inequalities from two rows of a simplex tableau, Proc. IPCO 2007, LNCS, vol. 4513, Springer, pp. 1--15]. We describe the facets of this mixed integer linear program via the extreme points of a well-defined polyhedron. We then utilize this description to give polynomial...

Source: http://arxiv.org/abs/1107.5068v1

19
19

Jul 20, 2013
07/13

by
Amitabh Basu

######
19

######
0

######
0

We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash [Linear programming in infinite dimensional spaces : theory and applications, Wiley 1987]. This result implies that if there is a duality gap between the...

Source: http://arxiv.org/abs/1304.3832v1

10
10.0

Sep 23, 2013
09/13

by
Amitabh Basu

######
10

######
0

######
0

Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by...

Source: http://arxiv.org/abs/1111.1780v2

9
9.0

Sep 22, 2013
09/13

by
Amitabh Basu

######
9

######
0

######
0

For a minimal inequality derived from a maximal lattice-free simplicial polytope in $\R^n$, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers $\R^n$. We then use this characterization to show that a minimal inequality derived from a maximal lattice-free simplex in $\R^n$ with exactly one lattice point in the relative interior of each facet has a unique minimal lifting if and only if all the vertices of the simplex are lattice...

Source: http://arxiv.org/abs/1103.4112v2

5
5.0

Sep 21, 2013
09/13

by
Amitabh Basu

######
5

######
0

######
0

We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos, and Vavasis and Ye.

Source: http://arxiv.org/abs/1204.2031v1

33
33

Jul 20, 2013
07/13

by
Amitabh Basu

######
33

######
0

######
0

Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to...

Source: http://arxiv.org/abs/1304.3030v1

6
6.0

Sep 24, 2013
09/13

by
Amitabh Basu

######
6

######
0

######
0

We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.

Source: http://arxiv.org/abs/1109.4184v1